#include <stdio.h>
#include <conio.h>
#include<windows.h>

#define max1 50
#define infinity 30000
#define TRUE 1
#define FALSE 0
int weight[max1][max1];

int VerNum;
		   
void dijkstra(int s, int t, int *shortest, int path[])
{
	int i, k, distn_i, ver_i, min, new_distn;
	int set[max1];
   int L[max1];

	for(i = 0; i < VerNum; i++)
	{
		set[i] = FALSE;
		L[i] = infinity;
	}
	set[s] = TRUE;
	L[s] = 0;
	ver_i = s;
	while(ver_i != t)
	{
		min = infinity;
		distn_i = L[ver_i];
		for(i = 0; i < VerNum; i++)
			if(set[i] == FALSE)
			{
				new_distn = distn_i + weight[ver_i][i];
				if(new_distn < L[i])
				{
					L[i] = new_distn;
					path[i] = ver_i;
				}
				if(L[i] < min)
				{
					min = L[i];
					k = i;
				}
			}
		ver_i = k;
		set[ver_i] = TRUE;
	}
	*shortest = L[t];
}

int main()
{
	
	int i1,i2;
	for(i1 = 0; i1 < max1; i1++)
		for(i2 = 0; i2 < max1; i2++)
			weight[i1][i2] = infinity;int choice, x, y, i, j;
    char c;
	int wt, shortest;
	int path[max1];
	int s, t;
	system("cls");
   VerNum = 0;

	do
	{
		printf("\nOptions:\n");
		printf("\n1: Set vertices number");
		printf("\n2: Add an edge");
		printf("\n3: Find shortest path");
		printf("\n0: Exit");
		printf("\nYour choice: ");
		scanf("%d", &choice);
		switch(choice)
		{
			case 1:
			{
					printf("\nEnter number of vertices: ");
					scanf("%d",&VerNum);
				break;
			}
			case 2:
			{
				printf("\nEnter 2 vertices of the edge: ");
				scanf("%d %d", &x, &y);
				if(x >= VerNum || y >= VerNum)
					printf("Error !");
				else
				{
					printf("Enter the weight of edge %d -> %d : ", x, y);
					scanf("%d", &weight[x][y]);
					weight[y][x]=weight[x][y];
				}
				break;
			}
			case 3:
			{
				printf("\nStarting vertice: ");
				scanf("%d", &s);
				printf("\nendding vetice: ");
				scanf("%d", &t);
				dijkstra(s, t, &shortest, path);
				printf("\nShortest path fromm %d->%d is: %d ", s, t, shortest);
				printf("\nCorrect way: ");
				i = t;
				while(i != s)
				{
					printf("%d <- ", i);
               i = path[i];
				}
				printf("%d", s);
				break;
			}
		}
	} while(choice != 0);
}
